Linear Secret Sharing Schemes

(updated )

$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\box#1{\delim[{#1}]} \gdef\floor#1{\delim\lfloor{#1}\rfloor} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\bbox#1{\delim{\llbracket}{#1}{\rrbracket}} \gdef\norm#1{\delim\|{#1}\|_{\max}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\setn#1{\mathcal{#1}} \gdef\T{\mathsf{T}} \gdef\Z{\mathrm{Z}} $$

Thank you Daniel Kales, Roman Walch and others from TACEO for many pointers and explanations.

An $n$-party secret sharing scheme is a pair of protocols encode and decode between $n$ parties. Where an entity (not necessarily a party) with a value $a$ can encode this to secret shares $s_0, …, s_{n-1}$ and distribute these to the $n$ parties. Given (a subset of) shares, the decode procedure reconstructs the original value.

Given a ring $𝕂$, usually $ℤ_{2^k}$ or some prime field $𝔽$.

Environment: We assume perfect synchronous private communication channels between all entities. In practice this is created using end-to-end encrypted connections.

Generic construction

Todo. This is similar to the generalization to Monotone/Extended Span Programs (MSP/ESP) Feh98 JSL21. CDM00. In CFIK03 it is stated they are in 1-1 correspondence with LSSSs, like I attempting here. The CFIK03 paper seems to have a good concise overview.

In CDN15 § 6.3 this is presented (though in field version). In particular it shows that any scheme leads to some form of multiplication when parties locally pair-wise multiply there shares that they have. See GCEPs on page 167 for a general presentation.

  1. Q. How does this generalize to rings?
  2. Q. How does this generalize to packed secrets?
  3. Q. How does this generalize to mixed encoding? (i.e. inputs a, b are in different schemes).

Q. What do adversary structures like $\mathcal Q_2$ mean intuitively?

Given a commutative ring $𝕂$ such a $ℤ/qℤ$. An $n$-party affine $s$-multi secret sharing scheme over $𝕂$ has a cleartext values in $𝕂^s$ and secrets in the set of tuples $\setn S = \prod_{i∈[0,n)} \setn S_i$ where $\setn S_i$ is the set of possible shares of party $i$. There is a randomized injective protocol $\mathsf{encode}_{r}: 𝕂^s → \setn S$ and a surjective function $\mathsf{decode}: \setn S → 𝕂^s$. Given $a ∈ 𝕂^s$, denote with $[a]$ an arbitrary element of $\setn S$ such that $\mathsf{decode}([a]) = a$.

The set of secrets $\setn S$ has operations to add two secrets and multiply secrets by an element of $𝕂^s$ such that $\setn S$ forms a $𝕂^s$-module. It is also has an affine action of $𝕂^s$ (i.e. scalar addition).

Assume (argument TBD) that $\setn S$ is a free module. This means it has a basis and can be represented as $𝕂^k$ for some $k$. Let's also assume $k=n$, $\setn S = 𝕂^n$ and $\setn S_i = 𝕂$. Given a basis on $\setn S$ we can represent secrets $[a] ∈ \setn S$ as elements in $𝕂^n$.

To do. These assumptions are overly restrictive and exclude replicated schemes where $\setn S_i = 𝕂^k$ for some $k$.

The $\mathsf{decode}$ function is a surjective linear map as for every element in $\setn S$ there is a pre-image and $\mathsf{decode}([a] + [b]) = a+b$ and $\mathsf{decode}(c ⋅ [a]) = c⋅ a$ for any $a,b,c ∈ 𝕂$. In the basis it is represented by a full-rank decoding matrix $\mat D ∈ 𝕂^{s × n}.$ such that

$$ a = \mathsf{decode}([a]) = \mat D ⋅ [a] $$

The null-space $\ker \mat D$ has dimension $n - s$. This null-space allows for multiple valid encodings of the same secret and hence provides the randomness required for secrecy. It is however useful set aside a subspace of dimension $n_c$ to be held zero, leaving dimension $n_r = n - s - n_c$. Picking a basis for the random and zero subspaces results in a matrix

To do. Even if $𝕂^n$ has a basis this does not guarantee $\ker \mat D$ has a basis. In fact, this appears not the case for additive sharing in $ℤ_{2^k}$.

$$ \begin{bmatrix} a \\ r \\ 0 \end{bmatrix} = \begin{bmatrix} \mat D \\ \mat R \\ \mat C \end{bmatrix} ⋅ [a] $$

where $\mat R ∈ 𝕂^{n_r × n}, \mat C ∈ 𝕂^{n_c × n}$. We can now specify the $\mathsf{encode}_r$ operation as solving the above equation for some $a$ and $r ∈ 𝕂^{n_r}$. The scheme is fully specified by $(𝕂, \mat D, \mat R, \mat C)$.

Q. What are the conditions for this to be solvable? For example the additive scheme with an even number of parties is not invertable in $ℤ_{2^k}$.

Note. It is not strictly necessary that randomness and constants are linearly separable, but this is what all protocols seem to do.

To do. Derive the threshold the scheme provides, and any mallicious resistance.

Q. There should be some requirement that the entries in $\mat D$ are all non-zero, or else there is degeneracy and fewer shares are required to learn about some secret. One way to approach define this might be to insist that each share value can set change any secret value. A similar argument applies to $\mat R$. Q. Does it matter if a combination of rows or columns has zeros? Q What are sufficient and minimal constraints of $\mat D, \mat R, \mat C$ to make schemes unconditionally secure with some threshold?

Q. Given an $n$-party scheme with $n$ shares we can recursively deal the shares with a $m$-party scheme to obtain $n⋅m$ shares. What are the properties of such recursive schemes? What sort of isomorphisms follow from it?

Concrete schemes

Additive sharing

A simple protocol to share a single secret $a$ among $n$ parties is to create $n$ random values $x_0, x_1, …, x_{n-1}$ such that $a = x_0 + x_1 + ⋯ + x_{n-1}$. This can be represented using the decoding matrix

$$ \mat D = \begin{bmatrix} 1 & 1 & 1 & ⋯ & 1 \end{bmatrix} $$

One basis for $\ker \mat D$ is the $(n-1) × n$ matrix:

$$ \mat R = \begin{bmatrix} 1 & 0 & 0 & ⋯ & -1 \\ 0 & 1 & 0 & ⋯ & -1 \\ 0 & 0 & 1 & ⋯ & -1 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & ⋯ & -1 \\ \end{bmatrix} $$

Q. In $ℤ_{2^{16}}$ there is no $\mat D^+$ for even values of $n$. In those cases it is not possible to construct an encoding that has $\mat R ⋅ \vec y = \vec 0$. Does this imply there is less entropy? How do we define the encode operation?

Shamir secret sharing

First introduced in Sha79, applied to MPC in BGW88, and generalized to multi-secrets in FY92. See also AL11 for a detailed description. Given a ring $𝕂$, the protocol works implicitly with polynomials in $𝕂[X]$. The protocol is specified by a set of secret and share evaluation points $\vec s, \vec x ⊂ 𝕂$ and such that all evaluation points are distinct. The multi-secret is represented as a polynomial $P ∈ 𝕂[X]$ such that each party's share $y_i = P(x_i)$ and the secrets are stored as $a_i = P()$

Recall the Vandermonde matrix $\mat V_{\vec x}$ for an evaluation basis $\vec x$ such that if $\vec c$ are the coefficients of a polynomial $P ∈ 𝕂[X]$ then $\vec y = \mat V_{\vec x} ⋅ \vec c$ computes the evaluations such that $y_i = P(x_i)$. This can also be seen as a transformation from monomial (coefficient) basis to an evaluation basis. It is given by

$$ \mat V_{\vec x} = \begin{bmatrix} 1 & x_0 & x_0^2 & x_0^3 & ⋯ \\ 1 & x_1 & x_1^2 & x_1^3 & ⋯ \\ 1 & x_2 & x_2^2 & x_2^3 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{bmatrix} $$

Consequently $\mat V_{\vec x}^{-1}$, which always exists if $𝕂$ is a field, transforms from evaluations to coefficients. We can use this to convert from the share evaluation basis to the secret evaluation basis. This gives our decoding matrix as $\mat D = \mat V_{\vec s} ⋅ \mat V_{\vec x}^{-1}$. We can compute the entries of the decoding matrix directly using the Lagrange interpolation formula:

$$ \mat D_{ij} = \mathrm{L}_j(s_i) = \prod_{k ∈ [0,n) ∖ j} \frac{s_i - x_k}{x_j - x_k} $$

This matrix exists if each $x_i - x_j$ is invertible in $𝕂$. They are non-zero by the requirement of distinctness, so the matrix always exists when $𝕂$ is a field. Unfortunately in the computationally interesting rings $ℤ_{2^k}$ there are no solutions with more than two points $x_i$.

A particularly useful basis for $\ker \mat D$ can be constructed by selecting the high coefficients.

$$ \begin{bmatrix} \mat D \\ \hline \mat R \\ \mat C\end{bmatrix} = \begin{bmatrix} \mat V_{\vec s} \\ \hline \begin{array}{cc} 0 & I & 0 \\ 0 & 0 & I \end{array} \end{bmatrix} ⋅ \mat V_{\vec x}^{-1} $$

By setting $\vec c = \vec 0$ we can restrict the degree of $P(X)$, which is the key to BGW Multiplication. Let $n_c$ be the size of $\vec c$, then

$$ \deg P ≤ n - n_c - 1 $$

Q. Can BGW multiplication be made to work with values of $\vec c$ other than $\vec 0$?

Q. Does this generalize to confluent Vandermonde matrices? I.e. we also include evaluations over formal derivatives of $P$ in our basis. (See Hermite interpolation)

Note. It is not possible to represent the additive scheme as a Shamir scheme. Consider the $n=2$ case, the Lagrange interpolation formula for $\mat D$ implies the unsolvable system

$$ \begin{aligned} 1 &= \frac{s_0 - x_1}{x_0 - x_1} & 1 &= \frac{s_0 - x_0}{x_1 - x_0} \end{aligned} $$

Useful Protocols

Dealing secrets

To input a value $\vec a$ the dealer who has the value generates shares $\vec y$ and distributes them to the parties. Note that the dealer can be one of the parties. Some protocols use this to distribute a share $y_i$ as a secret $[y_i]$, known as shares-of-shares.

Todo. Elaborate how this works for multi-secrets. Could set only the desired values and set the others to zero. Then add the secrets.

Dealing non-secret values

If a non-secret value $a$ needs to be input the trivial solution is to broadcast it to all parties. The value can then be used as cleartext in the protocols. But if the value is only used additively (i.e. it is not multiplied by a secret), it can also be dealt as a secret $[a]$. In GSZ20 it is observed that since this value is not really secret, we can use the $n_r$ degrees of freedom in the randomness to instead fix $n_r$ of the shares $y_i$ to constant values (typically zero) already known to those parties. This saves $n_r$ messages compares to plaintext broadcast.

To do. Explicit formulas.

Revealing secrets

An efficient protocol to open or reveal a secret is to send all shares to a single entity

Randomness generation

From DN07, BH08. It starts with the observation that for a suitable matrix $l×n$ matrix $\mat M$ (such as a Vandermonde matrix), we can generate $l ≤ n$ secret random values using only $n^2 - n$ messages with malicious security against $n - l$ adversaries. The protocol proceeds as follows.

  1. Each party $i$ picks a random number $r_i ∈_R 𝔽$ and secret shares it, creating $[r_i]$. This requires $n^2 - n$ messages.
  2. Each party locally computes $[\vec r'] = \mat M ⋅ [\vec r]$.

The vector $[\vec r']$ now has $l$ independent uniform random values. A variant of this protocol has the parties simultaneously compute $[\vec r]$ and $[\vec r]_{\deg < \frac n2}$, where the latter is a low degree Shamir secret encoding in the BGW sense.

This requires $\mat M$ to be hyper-invertable, meaning that each square submatrix is invertible. In CDN15 p. 186 it is claimed this is known as a 'regular matrix' and 'maximum distance seperable (MDS) matrix' in other fields.

Q. Are 'every square submatrix is invertible' and 'every submatrix is full-rank' equivalent? See CDN15 p 186. A. Yes. The $←$ case is trivial, for the other direction pick any maximal size square submatrix in the submatrix, this is invertible and hence the non-square matrix is full rank.

Q. How to generate all MDS matrices? Vandermonde ($x_i^j$), Cauchy ($\p{x_i - x_j}^{-1}$), and circulant matrices ($x_{i+j}$) are examples. Are MDS matrices closed under matrix or elementwise multiplication? Are the other transformations we can do that perserve the MDS property?

https://en.wikipedia.org/wiki/MDS_matrix

Local randomness generation

Simply set $y_i = r_i$ to create random $[r]$. Assumes semi-honest. Needs more nuance of there are constraints.

Replicated version party $i$ has key to PRNG $i$ and $i+1$.

Converting between $𝕂$-schemes

Given two different affine schemes $\mathcal A$, $\mathcal B$ over the same ring $𝕂$. We want to convert a secret $[a]_{\mathcal A}$ to $[a]_{\mathcal B}$. In CCD88, CDN01 the double-randomness protocol is introduced that works as follows:

  1. The parties generate a random secret $r$ simultaneously in both schemes $[r]_{\mathcal A}$, $[r]_{\mathcal B}$.
  2. The parties compute $[a + r]_{\mathcal A} = [a]_{\mathcal A} + [r]_{\mathcal A}$.
  3. The parties open this value to reveal $\p{a + r}$.
  4. The parties compute $[a]_{\mathcal B} = \p{a + r} - [r]_{\mathcal B}$.

Note that the first step can be done efficiently in batch as a preprocessing step. In GSZ20 (see also Esc23) it is observed that for step 3 it is more efficient to let a single party do the decoding and use secret sharing to deal $\p{\vec a + \vec r}$.

This is notably used in CCD88, DN07 with Shamir schemes to convert from a high-degree to a low-degree polynomials.

Note. This is very generic and the schemes don't need to be MPC schemes, as long as they are affine. This allows it to be used for conversion between, say a homomorphic encryption scheme and elliptic curves.

Converting between any schemes

Given sets $𝕂, 𝕃$ with secret sharing schemes $\mathcal K, \mathcal L$, and a function $f:𝕂 → 𝕃$, we want to convert $[a]_{\mathcal K}$ to $[f(a)]_{\mathcal L}$. Here is a template for a protocol:

  1. Each party computes $y_i' = f_i(y_i)$ and inputs $[y_i']_{\mathcal L}$.
  2. The parties compute $[a]_{\mathcal L} = \mathsf{decode}_{\mathcal K}([y_0']_{\mathcal L},[y_1']_{\mathcal L},…,[y_{n-1}']_{\mathcal L})$.

The key idea here is that $\mathsf{decode}_{\mathcal K}$ is computed in $\mathcal L$.

Q. When $𝕂 = 𝕃$ and the schemes are AMSSs, does $\mathsf{decode}_{\mathcal K}$ become a locally computable operation?

Converting between additive $ℤ_{2^k}$ and $ℤ_2^k$

Given $ℤ_{2^k}$ additive secret sharing scheme $\mathcal A$ and $ℤ_2^k$ scheme $\mathcal B$. Take twos-complement encoding $\mathsf{bits}_k: ℤ_{2^k} → ℤ_2^k$ and an $n$-input $k$-bit binary adder circuit $\mathsf{adder}_{nk}$.

  1. Each party computes $y_i' = \mathsf{bits}_k(y_i)$ and inputs $[y_i']_{\mathcal B}$.
  2. The parties compute $[a]_{\mathcal B} = \mathsf{adder}_{nk}([y_0']_{\mathcal B},[y_1']_{\mathcal B},…,[y_{n-1}']_{\mathcal B})$.

Converting between $ℤ_2^k$ and $ℤ_{2^k}$

Convert individual bits $[b_i]_{\mathcal A}$ and compute the sum $\sum_{i ∈ [0,k)} [b_i]_{\mathcal A}⋅2^i$.

Double randomness between rings?

Q Given secrets $[s], [r]$ over a ring $ℤ_m$. Is there a protocol to compute and reveal $\floor{\frac{s + r}{m}}$?

Given LSSSs with different moduli $m$ and $k$, and a secret $[s]_m$.

  1. Parties generate double randomness $[r]_m$, $[r]_k$ where $r ∈ [0,m)$.
  2. Parties compute $[s + r]_m$.
  3. Parties reveal $(s+r) \mod m$ and $q = \floor{\frac{s + r}{m}}$.
  4. Parties input $[s + r]_k$.
  5. Parties compute $[s+r]_k - [r]_k - q ⋅ m$.

Q. How much does $k$ reveal? Note that $k∈\ps{0,1}$ since $s + r < 2⋅p$, so it can not be more than one bit.

Note. The end result will be $s$ reduced modulo $q$, but this is intentional.

Intra-share matrix multiplication

BGW matrix multiplication

We would like a secure protocol for applying an arbitrary $n×n$ matrix to the secret shares:

$$ \vec y' = \mat M ⋅ \vec y $$

Each output share can depend on each input share, so it is clear some form of communication is required here. We can use secret sharing to create shares of each share, and then use the linearity of the encoding to compute each output share, and reveal this value to the party that should hold it.

One way to achieve this is to secret share each

  1. Each party $i$ shares it's share $y_i$ as a secret $[y_i]$, we now have $[\vec y]$.
  2. Each party locally computes $[\vec y'] = \mat M ⋅ [\vec y]$.
  3. The parties reveal $[y_i']$ to party $i$.

to do. Step 3 is unnecessary and only one round is required. See EKR18 § 3.3.

Q Does this generalize to other decoding matrices than ones constructed by Shamir?

Multiplication protocols

While affine transformations are trivially locally computed in all LSSSs, to compute arbitrary functions we also need the ability to multiply two secret values $[a]$, $[b]$ to get $[a⋅b]$.

A number of protocols exists, but they all share a perculiar feature: They first execute a round of communication to bring the parties in a specific state. This state is then consumed when do the multiplication.

Beaver multiplication triples

Bea91 presents a method to pre-compute a multiplication also known as circuit randomization. Generate random secrets $[a]$ and $[b]$ and pre-compute their product $[a⋅b]$ using any protocol. Then during the 'live' phase where the parties have $[x]$ and $[y]$ and want to compute $[x⋅y]$, they do the following:

  1. Compute $[x + a]$ and $[y + b]$ locally.
  2. Reveal $\p{x+a}$ and $\p{y+b}$ it to all parties.
  3. Compute $[x⋅y] = \p{x + a}⋅[y] - \p{y + b}⋅[a] + [a⋅b]$ locally.

The only live communication is revealing two secrets to all parties, which requires $2⋅(n^2 -n)$ messages. Note that the secrecy of the protocol depends on the triplet $([a], [b], [a⋅b])$ being used only once. A fresh triplet is required for each multiplication.

Q. Can this be adapted to allow for efficient dot-products like most other protocols? I.e. can we take a linear or affine combination of products with communication complexity in the size of the result? This likely also implies consuming correspondingly fewer triples.

Note. Some papers instead compute $[x⋅y] = \p{x + a}⋅\p{y + b} - \p{x + a}⋅[b] - \p{y + b}⋅[a] + [a⋅b]$ which also works, but requires one more multiplication.

Note. The dotproduct protocol in PSSY20 seems to do the sharing after computing the (intermediate) product. The intermediate is also linear, allowing them to aggregate it for efficient dot-products.

To do. It seems that in PSSY20 this is generalized by considering the state where $\p{x+a}$ is cleartext and $[a]$ secret it's own linear secret sharing scheme. They also extend it to 3,4 and $n$-way multiplication by preprocessing (many) more shares, e.g. $[a],[b],[c],[a⋅b],[b⋅c],[a⋅c],[a⋅b⋅c]$ for the 3-way case.

Q. Can any arithmetic circuit be computed one-round using LSSSs?

Replicated sharing

From BW98, Mau06, MR18. Consider an $3$-party additive secret sharing scheme such that the secret value is the sum of the shares, $a = a_0 + a_1 + a_2$, then the product of two secrets is

$$ \begin{aligned} a ⋅ b &= \p{a_0 + a_1 + a_2} ⋅ \p{b_0 + b_1 + b_2} \\ &= \phantom{+} \p{a_0 + a_1} ⋅ \p{b_0 + b_1} - a_1 ⋅ b_1 \\ &\phantom{=} + \p{a_1 + a_2} ⋅ \p{b_1 + b_2} - a_2 ⋅ b_2 \\ &\phantom{=} + \p{a_2 + a_0} ⋅ \p{b_2 + b_0} - a_0 ⋅ b_0 \\ \end{aligned} $$

If party $i$ knows the secret shares of $i$ and $i+1$ it can compute the $i$-th row of this product. Since these rows summed together produce the product value, they constitute valid shares for $[a⋅b]$. This leads to the following protocol (indices are taken modulo $n$):

  1. Party $i$ sends its shares $a_i, b_i$ to party $i-1$.
  2. Party $i$ computes $c_i = \p{a_i + a_{i+1}}⋅\p{b_i + b_{i+1}} - a_{i+1}⋅b_{i+1}$.

It is important to note that the first step reduces the treshold, as now any two parties can recover the secret where before all three where required.

Note. We can view the regular state and the replicated state as two different secret sharing schemes. A multiplication operation converts a replicated state into a regular one. The replication protocol re-establishes the replicated state.

Q. What re-randomization is required?

To generalize this to $n$ parties with a threshold of $t$ we need to find a number of shares $k$ and an assignment to parties such that for every combination $(i,j)$ of shares at least one party has those two shares, and no fewer than $t$ parties combined have all the shares. A combinatorial search gives the following as the smallest $t=3$ solution, it requires $10$ parties and $5$ shares assigned as:

$$ \ps{0, 1}, \ps{0, 2}, \ps{0, 3}, \ps{0, 4}, \ps{1, 2}, \ps{1, 3}, \ps{1, 4}, \ps{2, 3}, \ps{2, 4}, \ps{3, 4} $$

These are the edges of the $K_5$ graph. Similarly the $3$-party scheme is generated by the $K_3$ graph. Generally the full graph $K_k$ generates a replication protocol with

$$ \begin{aligned} n &= \frac{k⋅\p{k-1}}{2} & t &= \ceil{\frac{k}{2}} \end{aligned} $$

$$ \begin{array}{c|} k & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline n & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 \\ t & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5\\ \end{array} $$

Q. How does this relate to JSL21 § B.2? They cite in the intro Mau06 as the originator and [KRSW18], [SW19] and call the replication protocol 'KRSW'.

Todo. In Mau06 and others each party deals their partial result to all parties, which are then summed. This has different communication complexity then the AFL⁺16 MR18 protocol where each party adds randomized zero and shares with their neighbor. The summation of terms is implicitly performed on decoding. This is distinct enough to consider them separate variants (like BGW88 and CCD88 below).

Shamir multiplication

Consider a Shamir secret sharing schemes with $\vec s$ and $\vec x$. The parties have secrets $[a]$ and $[b]$ and wish to compute the product $[c] = [a⋅b]$. If they locally multiply shares such that $c_i = a_i ⋅ b_i$ they have constructed a polynomial

$$ P_c(X) = P_a(X)⋅P_b(X) \mod \Z_{\vec x}(X) $$

where $\Z_{\vec x}$ is the zero polynomial such that $\Z_{\vec x}(X) = \prod_{x ∈ \vec x} \p{X - x}$. To get the correct results we instead need to end up with a $P_c(X)$ such that

$$ P_c(X) = P_a(X)⋅P_b(X) \mod \Z_{\vec s}(X) $$

In BGW88, CCD88 it is noted this can be achieved by reducing the degrees of $P_a$ and $P_b$ such that their product is lower degree than $\deg \Z_{\vec x} = n$. Denote with $[–]_d$ the Shamir scheme restricted to degree at most $d$. Then elementwise multiplication of shares $[a]_k$, $[b]_l$ results in $[a⋅b]_{k+l}$ if $k+l < n$.

In BGW88, FY92, AL11 degree reduction to $d$ is achieved using the intra-share matrix multiplication protocol with the matrix $\mat M$ given by

$$ \mat M = \mat V_{\vec x} ⋅ \operatorname{diag}(\overbrace{1, 1, …, 1 }^{d+1}, \overbrace{0, 0, …, 0}^{n - d - 1}) ⋅ \mat V_{\vec x}^{-1} $$

In CCD88 and DN07 the degree reduction is instead achieved under the scheme conversion protocol.

Q. Instead of degree reduction, can we use other constraints on the scheme? The degree reduction aims to avoid the effects of the modular reduction, other schemes will instead need to correct for it. This seems like a linear problem.

Q. Is there any way this can be made to work for non-Shamir schemes?

The minimum and maximum degree for an $n$-party Shamir scheme with $s$ secrets and threshold $t$ is

$$ s + t - 2 ≤ d ≤ n - 1 $$

The number of minimum degree secret factors that can be multiplied before the product exceeds the degree capacity of the parameters is

$$ \floor{\frac{n - 1}{s + t - 2}} $$

Some optimal small-$n$ parameter choices are:

$$ \begin{array}{c|c:cc:ccc:} n & 2 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 5\\ s & 1 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 & 4\\ t & 2 & 2 & 2 & 2 & 3 & 2 & 2 & 3 & 2 & 2\\ \hline d_{\min} & 1 & 1 & 2 & 1 & 3 & 3 & 1 & 2 & 2 & 4 \\ d_{\max} & 1 & 2 & 2 & 3 & 3 & 3 & 4 & 4 & 4 & 4 \\ n_{\mathrm{mul}} & 1 & 2 & 1 & 3 & 1 & 1 & 4 & 2 & 2 & 1 \\ \end{array} $$

Q. What if we have an $s$-multi secret where we want to multiply all $s$ against the same value, encoded as a $s=1$ secret? We can alternatively encode it as a $s=2$ secret with the constraint that both are identical. This constraint acts much like a degree reduction. Then in the $n=4, t=2$ case we could multiply an $s=2$ secret times an (repeated) $s=1$ secret.

To do. Extensions like multi-variate polynomials, Hermite interpolation and recursive Shamir schemes.

References

https://pdf.sciencedirectassets.com/271602/1-s2.0-S0166218X05X03134/1-s2.0-S0166218X05002428/main.pdf

D. Beaver, A. Wool, , Advances in Cryptology—EUROCRYPT ’98, Lecture Notes in Computer Science, vol. 1403, Springer, Berlin, 1998, pp. 25–35.

Remco Bloemen
Math & Engineering
https://2π.com